#include <iostream>
#include <string>
#include <map>
using namespace std;

typedef enum{Link, Thread} NodeTag;

class TreeNode
{
private:
    char data;              //值
    TreeNode* leftChild;    //左孩子
    TreeNode* rightChild;   //右孩子
    NodeTag lTag, rTag;     //线索Tag

    friend class MyTree;    //树类
public:
    TreeNode(char, TreeNode*, TreeNode*, NodeTag, NodeTag);
    ~TreeNode();

    void printNode();
    
};

class MyTree
{
private:
     TreeNode* root;        //根指针
     bool isThread;         //线索二叉树标志
public:
    MyTree();               //无参构造
    MyTree(const char[]);   //构造函数
    MyTree(const MyTree&);  //拷贝函数
    ~MyTree();              //析构函数
    TreeNode* constructFromPreorder(const char preOrder[], int& idx);
    TreeNode* copyTree(const TreeNode* node);
    void deleteTree(TreeNode* node);
    void preOrderTraverse();    //前序遍历
    void inOrderTraverse();     //中序遍历
    void postOrderTraverse();   //后序遍历
    int countLeaf();            //叶结点计数
    int countHeight();          //计算树的深度
    bool isThreadedTree();      //判断是否为线索二叉树
    bool inOrderThreading();    //线索化
    TreeNode& locateNode(const char&);  //结点定位
    TreeNode& preNode(const TreeNode&); //获取前驱结点
    TreeNode& nextNode(const TreeNode&);//获取后继结点
    TreeNode& locateNodeInNormalTree(TreeNode* node, const char& v);
    TreeNode& locateNodeInThreadedTree(const char& v);
    void inOrderThreadingHelper(TreeNode* node, TreeNode*& pre);
    void inOrderNormalTraverse(TreeNode* node);
    void inOrderThreadedTraverse(TreeNode* node);
};

// 霍夫曼树的节点结构
struct HuffmanNode {
    int value;        // 节点的权重（重要度）
    HuffmanNode* left;  // 左子树
    HuffmanNode* right; // 右子树
    // 构造函数
    HuffmanNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// 用于比较节点权重的优先队列比较器
struct CompareNode {
    bool operator()(HuffmanNode* left, HuffmanNode* right) {
        return left->value > right->value;
    }
};

class HuffmanTree
{
private:
    //添加必要的数据成员
    HuffmanNode* root;  // 霍夫曼树的根节点
    map<int, string> codes;  // 存储节点值到编码的映射
    void generateCodes(HuffmanNode* node, string code);
    // 销毁树的递归函数
    void deleteTree(HuffmanNode* node);
public:
    HuffmanTree(const int&,const int[]);    //构造函数
    ~HuffmanTree();     //析构函数

    //输出哈夫曼编码
    //格式为：每行输出一个节点，节点排序递减
    //节点1值：编码
    //节点2值：编码
    //....
    //cpp中未给出该函数，遵守输出格式规范
    void printHuffmanCodes();   

 
};


